package com.lc.hot100.lc139;

import java.util.*;

public class Main {
	public static void main(String[] args) {
		
		String s = "123456789";
		System.out.println(s.substring(1, 9));
		
	}
}

class Solution {
    public boolean wordBreak(String s, List<String> wordDict) {
        Set<String> set = new HashSet<>(wordDict);
        int n = s.length();
        boolean[] f = new boolean[n + 1];
        f[0] = true;
        
        for (int i = 0; i <= n; i ++) {
        	for (int j = 0; j < i; j ++) {
        		if (f[j] && set.contains(s.substring(j, i))) {
        			f[i] = true;
        			break;
        		}
        	}
        }
        
        
        return f[n];
    }
}